/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-12 10:56:41
 * @LastEditors: lily
 * @LastEditTime: 2021-04-12 14:40:38
 */
/*
 * @lc app=leetcode.cn id=33 lang=javascript
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

//  思路：二分查找
//  先看哪那一部分是有序的，再看taget落入了哪一个部分，再进行二分查找

//  复杂度：O(logn)  O(1)

var search = function (nums, target) {
    let start = 0, end = nums.length - 1
    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2)
        if (nums[mid] === target) {
            return mid
        }
        // start-mid 有序
        if (nums[mid] >= nums[start]) {
            // target在有序的部分
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }
        // mid-end有序
        else {
            // target在有序的部分
            if (target <= nums[end] && target > nums[mid]) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return -1
};
// @lc code=end

console.log(search([5, 1, 3], 3));